package leetcode.editor.cn;

//给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 
//
// 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nu
//ms2 的元素。
//
// 示例 1：
//输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
//输出：[1,2,2,3,5,6]
// 
// 示例 2：
//输入：nums1 = [1], m = 1, nums2 = [], n = 0
//输出：[1]
//
// 提示： 
// nums1.length == m + n
// nums2.length == n 
// 0 <= m, n <= 200 
// 1 <= m + n <= 200 
// -10^9 <= nums1[i], nums2[i] <= 10^9
// 
// Related Topics 数组 双指针 排序 
// 👍 1006 👎 0


import java.util.Arrays;

public class T88MergeSortedArray {

    public static void main(String[] args) {
        Solution solution = new T88MergeSortedArray().new Solution();
        int[] nums1 = {6,0};
        int[] nums2 = {1};
        int m = 1;
        int n = 1;
        solution.merge4optimization_1(nums1, m, nums2, n);
        solution.print(nums1);
    }

class Solution {
    /**
     * <p>两个数组都是有序数组的，且nums1的后面几个位置的元素是可以替换的。</p>
     * <p>利用指针。<br/>
     * 三个指针，第一个指针指向nums1数组的最后一个元素；第二个指针指向nums1数组的最后一个有效元素；第三个指针指向nums2的最后一个元素
     * 然后开始比较，将第二个指针的元素和第三个指针的元素比较，大的数放在第一个指针处，并且第一个指针和刚在比较大的指针都左移一位，再继续比较
     * 循环往复。<br/>步骤如下：</p>
     *
     * {1,2,5,0,0,0};
     * <br/>
     * {2,3,6};
     * <hr/>
     *
     *
     * {1,2,5,0,0,6};
     * <br/>
     * {2,3};
     * <hr/>
     *
     * {1,2,0,0,5,6};
     * <br/>
     * {2,3};
     * <hr/>
     *
     * {1,2,0,3,5,6};
     * <br/>
     * {2};
     * <hr/>
     *
     * {1,2,2,3,5,6};
     *
     */
    public void merge4optimization_1(int[] nums1, int m, int[] nums2, int n) {
        int i = nums1.length;
        while (n > 0) {
            if (m > 0 && nums1[m-1] > nums2[n-1]) {
                nums1[--i] = nums1[--m];
            }else {
                nums1[--i] = nums2[--n];
            }
        }
    }

    public void merge4optimization(int[] nums1, int m, int[] nums2, int n) {
        if (nums1.length < nums2.length || nums1.length != m + n) {
            return;
        }
        if (n == 0) {
            return;
        }
        if (m == 0) {
            for (int i = 0; i < nums1.length; i++) {
                nums1[i] = nums2[i];
            }
            return;
        }
        int up = m - 1;
        int down = n - 1;
        int last = m + n - 1;
        while (last >= m - 1 && down >= 0) {
            if (nums1[up] > nums2[down]) {
                nums1[last] = nums1[up];
                if (up == 0) {
                    nums1[up] = nums2[down];
                    break;
                }
                up--;
            } else {
                nums1[last] = nums2[down];
                down--;
            }
            last--;
        }
    }

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (nums1.length < nums2.length || nums1.length != m + n) {
            return;
        }
        //第一步，先将 nums2直接放入到nums1
        for (int i = 0; i < nums2.length; i++) {
            nums1[m + i] = nums2[i];
        }
        //第二步，然后对nums1进行排序
        Arrays.sort(nums1);
        //打印
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < nums1.length; i++) {
            if (i == nums1.length - 1) {
                sb.append(nums1[i]+"]");
            }else {
                sb.append(nums1[i] + ",");
            }
        }
        System.out.println(sb.toString());
    }

    private void print(int[] nums1) {
        //打印
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < nums1.length; i++) {
            if (i == nums1.length - 1) {
                sb.append(nums1[i] + "]");
            } else {
                sb.append(nums1[i] + ",");
            }
        }
        System.out.println(sb.toString());
    }


}


}